#define _CRT_SECURE_NO_WARNINGS 1

//c++
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x)
    {
        struct ListNode* lessHead = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* greaterHead = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* lessTail = lessHead;
        struct ListNode* greaterTail = greaterHead;
        lessTail->next = NULL;
        greaterTail->next = NULL;
        struct ListNode* cur = pHead;
        while (cur) {
            if (cur->val < x) {
                lessTail->next = cur;
                lessTail = lessTail->next;
            }
            else {
                greaterTail->next = cur;
                greaterTail = greaterTail->next;
            }
            cur = cur->next;
        }
        lessTail->next = greaterHead->next;
        greaterTail->next = NULL;
        struct ListNode* list = lessHead->next;
        free(lessHead);
        free(greaterHead);
        return list;
    }
};